package qsort;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;

public class QuickSort implements Runnable {
	ArrayList<Record> SortList; 
	int start_position ; 
	int end_position ;
	
	public QuickSort(ArrayList<Record> _SortList, int start, int end){
		this.SortList = _SortList;
		this.start_position = start; 
		this.end_position = end; 
	}

	private int partition(int start, int end) {
		// Move the pivot to the end 
		Record valueOfLast = SortList.get(end);
		int currentPointer = start; 
		for (int i =start; i<end; i++){
			Record currentValue = SortList.get(i);
			if (currentValue.compareTo(valueOfLast)<0){
				// Swap 
				Collections.swap(SortList, currentPointer, i);
				// Increase current pointer 
				currentPointer++;
			}
		}
		// Move back pivot to the final position 
		Collections.swap(SortList, currentPointer, end); 
		return currentPointer;
	}

	public void IterativeQuickSort(){
		// Use stack instead of recursive 
		Stack<Integer> stack = new Stack<Integer>();
		// Size of the whole list 
		stack.push(start_position); // start 
		stack.push(end_position); // end
		
		while (stack.size()>0){
			
			// careful with the order 
			int end = stack.pop(); 
			int start = stack.pop();
		
			// find pivot elements 
			int pivotPosition = partition(start,end);
			
			// Push the left part to stack
			if (start < pivotPosition -1 ){
				stack.push(start);
				stack.push(pivotPosition -1);
			}
			
			// Push the right part to stack 
			if (pivotPosition + 1 < end){
				stack.push(pivotPosition + 1);
				stack.push(end);
			}
		}
		
		// Test ONLY 
//		for (int i=0; i<SortList.size(); i++){
//			System.out.println(SortList.get(i).getData());
//		}
		
	}
	public void run() {
		// TODO Auto-generated method stub
		IterativeQuickSort();
	}

}
